package 题目集.位运算.集合论;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * https://leetcode.cn/problems/find-the-prefix-common-array-of-two-arrays/description/
 * 题意：用一个数组记录前i个元素的共同元素个数
 */
public class ch03_找到两个数组的前缀公共数组 {

    /**
     * 范围很小，所以可以用位图代替哈希表
     * 公共元素的数量=两个集合中交集的元素个数
     * @param a
     * @param b
     * @return
     */
    public int[] findThePrefixCommonArray(int[] a, int[] b) {
        long aset = 0, bset = 0;
        int[] ans = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            aset |= 1L << a[i];
            bset |= 1L << b[i];
            ans[i] = Long.bitCount(aset&bset);
        }
        return ans;
    }


    @Test
    public void test() {
        int[] a = {1, 3, 2, 4};
        int[] b = {3, 1, 2, 4};
        int[] ans = findThePrefixCommonArray(a, b);
        System.out.println(Arrays.toString(ans));

    }
}
